#! /usr/bin/env python3
# description: 通过希尔排序对乱序列表排序

import random


def insertion_sort(arr: list, start: int, step: int):
    """插入排序"""
    size = len(arr)
    for i in range(start, size, step):
        # 与有序数组的最后一个元素开始比较
        # 此处的step为变量，当增量为1时，则为普通的插入排序
        j = i - step
        # 进入的条件：待插入数据比最后一数小且比较的数据的索引不小于0
        while arr[j+step] < arr[j] and j >= 0:
            arr[j], arr[j+step] = arr[j+step], arr[j]
            j -= step


def shell_sort(arr: list):
    """希尔排序"""
    num = len(arr) // 2
    # 当增量为0时，退出循环
    while num:
        print("增量为：", num)
        # 依次对分组后的数组进行插入排序
        for i in range(num):
            print("\t待分组的数组", arr[i::num])
            insertion_sort(arr, i, num)
            print("\t排序后的数组", arr[i::num])
            print("整个数组的结果", arr, '\n')
        num = num // 2
    
#arr = [10, 9, 3, 8, 2, 4, 3, 7, 1, 5, 11]
arr = [ random.randint(1, 100) for i in range(25) ]
print("待排序数组为", arr)
shell_sort(arr)
print(arr)

